package LearnAlgorithm.j_动态规划and贪心算法;

import java.util.Scanner;

/*
Serling公司购买长钢条，将其切割为短钢条出售。
切割工序本身没有成本支出。
公司管理层希望知道最佳的切割方案。
假定我们知道Serling公司出售一段长为i英寸的钢条的价格为pi(i=1,2,…，单位为美元)。
钢条的长度均为整英寸。

长度i 	| 1  | 2  | 3  | 4  | 5  | 6  | 7  | 8  | 9  | 10 |
		| -  | -  | -  | -  | -  | -  | -  | -  | -  | -  |
价格pi 	| 1  | 5  | 8  | 16 | 10 | 17 | 17 | 20 | 24 | 30 |

钢条切割问题是这样的：
给定一段长度为n英寸的钢条和一个价格表pi(i=1,2,…n)，
求切割钢条方案，使得销售收益rn最大。
注意，
如果长度为n英寸的钢条的价格pn足够大，
最优解可能就是完全不需要切割!

10
1 5 8 16 10 17 17 20 24 30

37
 */
public class g钢条切割byDP {
	public static void main(String[] args) {
		g钢条切割byDP test = new g钢条切割byDP();
		test.useDP();
	}
	
	public void useDP() {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int[] price = new int[N];
		for (int i = 0; i < N; i++) {
			price[i] = scanner.nextInt();
		}
		int[] dp = new int[N + 1];//一定N + 1;为了让长度=N的情况能考虑
		for (int i = 0; i < price.length; i++) {
			dp[i] = -1;
		}
		int res = DP(N, price, dp);
		System.out.println(res);
	}
	
	public int DP(int length, int[] price, int[] dp) {
		int res = 0;
		dp[0] = 0;//代表没有钢条，那就价值是0呗
		//从有最小钢条开始尝试；currentLength = 1
		for (int currentLength = 1; currentLength <= length; currentLength++) {//currentLength是当前尝试的“假设就只有这么长钢条A”
			l1 : for (int segment = 1; segment <= currentLength; segment++) {//segment是在A长度中：固定片段的长度，也称需要查price[]表中价值的长度
				dp[currentLength] = Math.max(
						price[segment - 1] + dp[currentLength - segment],//查price表的价值 + 剩下部分的最大价值
						dp[currentLength]//不切的话，当前的“A”的价值v；v其实已经存在了dp[]中，所以我们直接查dp[]
						//dp[currentLength]在l1循环中，第一次循环的时候，初始值是-1
						//所以Math.max()的结果一定是price[segment - 1] + dp[currentLength - segment]
						//但后面的循环就不一定非得是price[segment - 1] + dp[currentLength - segment]
						//所以才运用Math.max()
						//l1循环考虑了不切的情况：当随着循环次数增加，segment = currentLength时，就就代表了不切
						//segment = currentLength时，price[segment - 1] + dp[currentLength - segment] = “currentLength这个长度在price表中的价值” + 0
						);
			}
		}
		return dp[length];
	}
}
